home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / dp_hash.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  4.6 KB  |  225 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  dp_hash.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_DP_HASH_H
  17. #define LEDA_DP_HASH_H
  18.  
  19. //------------------------------------------------------------------------------
  20. // Dynamic Perfect Hashing
  21. //
  22. // Michael Wenzel          ( 1990/91 )
  23. //------------------------------------------------------------------------------
  24.  
  25.  
  26. #include <LEDA/basic.h>
  27.  
  28.  
  29. // ---------------------------------------------------------------
  30. // declarations
  31. // ---------------------------------------------------------------
  32.  
  33.  
  34. class headertable;
  35. class subtable;
  36. class dp_hash;
  37.  
  38. typedef headertable* htp;
  39. typedef subtable* stp;
  40.  
  41. #define EMPTY (GenPtr(2147483648))
  42. #define maxuni 2147483647
  43.                                 // #define maxprim 2147483659
  44.                 // aber kleiner wegen random-Funktion
  45. #define maxprim 2147483647
  46. #define wursechs 2.44948974278
  47.  
  48.  
  49.  
  50.  
  51. // --------------------------------------------------------------
  52. // class headertable
  53. //
  54. // Items werden auf Headertables gehasht,
  55. // die sie dann injektiv auf Subtables verteilen
  56.  
  57. class headertable {
  58.  
  59.   unsigned kj;                     // Multiplikator
  60.   int wj;                          // Anzahl Elemente in Tafel
  61.   int mj;                          // max. Anzahl Elemente
  62.   stp tj;                          // Startpunkt der Subtables
  63.  
  64.   friend class b_dict;
  65.   friend class dp_hash;
  66.   friend class subtable;
  67.  
  68.   stp lookup(GenPtr );
  69.  
  70.   bool insert(GenPtr ,GenPtr ,stp& ,int& ,bool& ,stp ,stp );
  71.   int dinsert(GenPtr ,GenPtr ,stp ,stp& ,stp& );
  72.  
  73.   bool del(GenPtr ,stp ,stp ); 
  74.   int give_elements(stp& ,stp ,stp );  
  75.  
  76.  
  77.   headertable()
  78.     { 
  79.       kj = wj = mj=0; 
  80.       tj=0;   
  81.      }
  82.  
  83. };
  84.  
  85. // --------------------------------------------------------------
  86. // class subtable
  87. //
  88. // Jedes Subtableelement ist leer,
  89. // oder von der Headertable wird genau ein Element    
  90. // auf eine Position gehasht
  91.  
  92. class subtable {
  93.  
  94.   GenPtr ke;
  95.   GenPtr inf;
  96.  
  97.   friend class b_dict;
  98.   friend class dp_hash;
  99.   friend class headertable;
  100.  
  101.   void set_s(GenPtr a,GenPtr b)
  102.     {
  103.        ke=a; inf=b; }
  104.  
  105.   void clear()
  106.     { 
  107.        ke=EMPTY; inf=0; }
  108.  
  109.   subtable()
  110.     {  
  111.        ke=EMPTY; inf=0; }
  112.  
  113.   subtable(GenPtr a ,GenPtr b )
  114.     {  
  115.        ke=a; inf=b; }
  116.  
  117.   subtable(subtable& s)
  118.     {  
  119.        ke=s.ke;
  120.        inf=s.inf; }
  121.  
  122.    subtable& operator=(subtable& s)
  123.     {
  124.        ke=s.ke;
  125.        inf=s.inf;
  126.        return *this; }
  127.  
  128.  
  129.   public:
  130.  
  131.   GenPtr key() { return ke; }
  132.  
  133.   GenPtr info() { return inf; }
  134.  
  135. };
  136.  
  137. // ------------------------------------------------------------------
  138. // class dp_hash
  139. //
  140. // alle Informationen fuer das Dictionary
  141. // Elemente werden auf Headertables gehasht, 
  142. // die dann die Elemente weitergeben
  143. // Der Platzverbrauch der Headertables wird kontrolliert
  144.  
  145.  
  146. class dp_hash {
  147.  
  148.   htp* htablep;      // Feld von Zeigern auf Headertables
  149.              // leere Headertables werden nicht angelegt
  150.  
  151.   unsigned k;        // Verteilungsfunktion (k*x)%p%sM
  152.  
  153.   int n;             // Anzahl Elemente im Dictionary
  154.  
  155.   int M;             // Anzahl Elemente, die momentan bzgl.
  156.              // Platzverbrauch mit Wahrscheinlichkeit >= 0.5
  157.              // abgespeichert werden koennen ( ohne Rehash )
  158.  
  159.   int sM;            // Anzahl Headertables
  160.  
  161.   int bed;           // Kontrolle des Platzverbrauchs
  162.  
  163.   stp anf,wo,ende;   // zur Speicherverwaltung beim Rehash
  164.  
  165.  
  166.  
  167.   stp  rehash_all(GenPtr ,GenPtr );
  168.  
  169.  
  170.   virtual void clear_key(GenPtr&)const {}
  171.   virtual void clear_inf(GenPtr&)const {}
  172.  
  173.   virtual void copy_key(GenPtr&) const {}
  174.   virtual void copy_inf(GenPtr&) const {}
  175.  
  176. protected:
  177.  
  178.   stp item(void* p) const { return stp(p); }
  179.  
  180. public:
  181.  
  182.   stp first_item() const
  183.   { error_handler(1,"sorry, dp_hash::first_item not implemented");
  184.     return nil;
  185.    }
  186.  
  187.   stp next_item(stp) const
  188.   { error_handler(1,"sorry, dp_hash::next_item not implemented");
  189.     return nil;
  190.    }
  191.  
  192.   dp_hash& operator=(const dp_hash&) 
  193.   { error_handler(1,"sorry, dp_hash::operator= not implemented");
  194.     return *this;
  195.    }
  196.  
  197.   GenPtr  key(stp it)  const { return it->ke; }
  198.   GenPtr  inf(stp it)  const { return it->inf; }
  199.   GenPtr& info(stp it) const { return it->inf; }
  200.  
  201.   stp  insert(GenPtr,GenPtr );
  202.   void del(GenPtr);
  203.  
  204.   void del_item(stp it) { del(it->ke); }
  205.  
  206.   stp  lookup(GenPtr ) const;
  207.  
  208.   stp  change_inf(GenPtr ,GenPtr );
  209.  
  210.   int  size() const { return n; }
  211.  
  212.   void clear();
  213.  
  214.  
  215.   dp_hash();
  216.   dp_hash(int ,GenPtr* ,GenPtr* );
  217.   virtual ~dp_hash();
  218.  
  219.  
  220.   friend class b_dict;
  221.  
  222. };
  223.  
  224. #endif
  225.